<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>快速排序</title>
  </head>
  <body></body>
  <script>
    const array = [2, 4, 1, 3, 5];

    function quick_sort(array, start, end) {
      console.log("*************************************************");
      console.log(`这一轮排序区间是：[${start}, ${end}]`);

      if (start >= end) {
        console.log(`排序区间的起始索引大于等于结束索引，表示排序区间长度小于等于 0，结束排序`);
        return;
      }

      console.log("原数组", array);

      // 获取首尾排序指针索引，保留排序比较的首尾起始索引
      let left = start;
      let right = end;

      let key = array[left];
      console.log(`获取排序部分起始索引对应值为基础值`, `起始索引：${left}，基础值：${key}`);

      while (left < right) {
        console.group("尾部比较");
        console.log(`沿排序部分尾部依次向前比较，大于等于基础值的位置不变，小的与起始索引位置值覆盖`);

        while (key <= array[right] && left < right) {
          // 判断 left 必须小于 right，否则，就会首尾概念错误
          console.log(`尾部比较值：${array[right]}，被比较基础值：${key}`);
          console.log(`尾部比较值大于等于基础值，尾部指针索引 ${right} 减一，继续向前查找`);
          right--;
        }
        console.log(
          `找到一个较小值：${array[right]}，对应索引：${right}；进行覆盖；被覆盖索引位置：${left}，被覆盖值：${array[left]}`
        );
        array[left] = array[right];
        console.groupEnd();
        console.log(`尾部比较覆盖一次完成后新数组为`, array);

        console.group(`头部比较`);
        console.log(`沿排序部分头部依次向后比较，小于等于基础值的位置不变，大于的与起始索引位置值覆盖`);
        while (array[left] <= key && left < right) {
          // 判断 left 必须小于 right，否则，就会首尾概念错误
          console.log(`头部比较值：${array[left]}，被比较基础值：${key}`);
          console.log(`头部比较值小于等于基础值小，头部指针索引 ${left} 加一，继续向后查找`);
          left++;
        }
        console.log(
          `找到一个较大值：${array[left]}，对应索引：${left}；进行覆盖；被覆盖索引位置：${right}，被覆盖值：${array[right]}`
        );
        array[right] = array[left];
        console.groupEnd();
        console.log(`头部比较覆盖一次完成后新数组为`, array);
      }

      array[left] = key;
      console.log(`将基础值 ${key} 归位到数组索引位置 ${left} 内，数组值为`, array);

      quick_sort(array, start, left - 1);
      quick_sort(array, right + 1, end);
    }

    quick_sort(array, 0, array.length - 1);
  </script>
</html>
